//
// Created by cheng on 2021/03/09.
//

#ifndef ALDS_HEAP_H
#define ALDS_HEAP_H
#include <iostream>

template<class HDataType>
class Heap {
private:
    HDataType* data;
    int size{};
    int capacity{};
    const int CapacitySize = 50;

public:
    /**
     * 默认无参构造函数
     */
    Heap() {
        this->capacity = CapacitySize;
        this->size = 0;
        this->data = new HDataType[this->capacity];
        this->data[0] = 0;
    };

    /**
     * 数组构造函数
     * @param arr 数组
     * @param len 数组长度
     */
    Heap(const HDataType *arr, const int len) {
        this->capacity = CapacitySize;
        this->data = nullptr;

        while (this->capacity <= len) {
            this->capacity += CapacitySize;
        }
        this->data = new int[this->capacity];
        this->data[0] = -1;
        for (int i = 0; i < len; i++) {
            this->data[i+1] = arr[i];
        }
        this->size = len;
    }

    /**
     * 完全复制heap构造
     * @param heap
     */
    Heap(const Heap<HDataType> &heap) {
        this->data = new HDataType[heap.capacity];
        this->capacity = heap.capacity;
        this->size = heap.size;
        this->data[0] = -1;
        for (int i = 1; i <= heap.size; i++) {
            this->data[i] = heap.data[i];
        }
    }

    /**
     * 析构函数
     */
    ~Heap()  {
        delete[] this->data;
        this->data = nullptr;
        this->size = this->capacity = 0;
    }

    /**
     * 输出Heap的结构
     */
    void PrintHeap() {
        std::cout << "Heap: { \n";
        for (int i = 1; i <= this->size; i++, std::cout << ";\n") {
            auto parent = GetParent(i);
            auto lChild = GetLChild(i);
            auto rChild = GetRChild(i);
            std::cout << "\tnode " <<  i <<  ": key = " <<  this->data[i];
            if (parent != 0) {
                std::cout << ", parent key: " << this->data[parent];
            }
            if (lChild != 0) {
                std::cout << ", lChild key: " <<  this->data[lChild];
            }
            if (rChild != 0) {
                std::cout << ", rChild key: " <<  this->data[rChild];
            }
        }
        std::cout << "};\n";
    }
    void PrintHeap(const std::string& name) {
        std::cout << name <<": { \n";
        for (int i = 1; i <= this->size; i++, std::cout << ";\n") {
            auto parent = GetParent(i);
            auto lChild = GetLChild(i);
            auto rChild = GetRChild(i);
            std::cout << "\tnode " <<  i <<  ": key = " <<  this->data[i];
            if (parent != 0) {
                std::cout << ", parent key: " << this->data[parent];
            }
            if (lChild != 0) {
                std::cout << ", lChild key: " <<  this->data[lChild];
            }
            if (rChild != 0) {
                std::cout << ", rChild key: " <<  this->data[rChild];
            }
        }
        std::cout << "};\n";
    }

    /**
     * 输出Heap的数据
     */
    void PrintData() {
        std::cout << "HeapData:{ ";
        for (int i = 1; i <= this->size; i++) {
            std::cout << this->data[i] << " ";
        }
        std::cout << "};\n";
    }
    void PrintData(const std::string& name) {
        std::cout << name << ":{ ";
        for (int i = 1; i <= this->size; i++) {
            std::cout << this->data[i] << " ";
        }
        std::cout << "};\n";
    }

    /**
     * 获取父节点下标
     * @param cur
     * @return
     */
    int GetParent(int cur) {
        return cur < 2 ? 0 : cur/2;
    }

    /**
     * 获取左孩子节点下标
     * @param cur
     * @return
     */
    int GetLChild(int cur) {
        int a = cur*2;
        return a > this->size ? 0 : a;
    }

    /**
     * 获取又孩子节点下标
     * @param cur
     * @return
     */
    int GetRChild(int cur) {
        int a = cur*2+1;
        return a > this->size ? 0 : a;
    }

    /**
     * 在堆末尾添加元素
     * @param key
     */
    void Insert(const HDataType &key) {
        // 如果当前堆为空
        if (this->data == nullptr) {
            this->capacity = CapacitySize;
            this->data = new HDataType[CapacitySize];
            this->size = 0;
        }
        // 如果当前的堆满了,则扩容
        if (!this->capacity > this->size) {
            this->capacity += CapacitySize;
            auto temp = new HDataType[this->capacity];
            for (int i = 0; i <= this->size; i++) {
                temp[i] = this->data[i];
            }
        }
        // 在堆的最后添加元素key
        this->data[++(this->size)] = key;
    }

    /**
     * 生成一个大根堆
     * @param arr
     * @param len
     * @return
     */
    static Heap<HDataType>* MaxHeap(const HDataType *arr, int len) {
        // 构建一个新堆
        auto heap = new Heap<HDataType>(arr, len);
        // 从堆的中间节点开始依次向前遍历，构建大根堆
        for (int i = heap->size/2; i > 0; i--) {
            heap->MaxHeapify(i);
        }
        return heap;
    }
    static Heap<HDataType>* MaxHeap(Heap<HDataType> H) {
        auto heap = new Heap<HDataType>(H);
        for (int i = heap->size/2; i > 0; i--) {
            heap->MaxHeapify(i);
        }
        return heap;
    }

    /**
     * 生成一个小根堆
     * @param arr
     * @param len
     * @return
     */
    static Heap<HDataType>* MinHeap(const HDataType *arr, int len) {
        // 构建一个新堆
        auto heap = new Heap<HDataType>(arr, len);
        // 从堆的中间节点开始依次向前遍历，构建小根堆
        for (int i = heap->size/2; i > 0; i--) {
            heap->MinHeapify(i);
        }
        return heap;
    }
    static Heap<HDataType>* MinHeap(Heap<HDataType> H) {
        // 构建一个新堆
        auto heap = new Heap<HDataType>(H);
        // 从堆的中间节点开始依次向前遍历，构建大根堆
        for (int i = heap->size/2; i > 0; i--) {
            heap->MinHeapify(i);
        }
        return heap;
    }

    /**
     * 大根堆添加元素
     * @param key
     */
    void InsertInMaxHeap(HDataType key) {
        Insert(key);
        // 向前遍历，与父节点作比较，若比父节点大则交换
        for (int i = this->size, parentIndex = GetParent(i);
             i > 1 && this->data[i] > this->data[parentIndex];
             i = parentIndex, parentIndex = GetParent(i)) {
            std::swap(this->data[i], this->data[parentIndex]);
        }
    }

    /**
     * 小根堆添加元素
     * @param key
     */
    void InsertInMinHeap(HDataType key) {
        Insert(key);
        for (int i = this->size, parentIndex = GetParent(i);
             i > 1 && this->data[i] < this->data[parentIndex];
             i = parentIndex, parentIndex = GetParent(i)) {
            std::swap(this->data[i], this->data[parentIndex]);
        }
    }

    /**
     * 取出大根堆堆顶元素
     * @return
     */
    HDataType ExtractFromMaxHeap() {
        HDataType max;
        if (this->size < 1) {
            max = (HDataType)0;
        } else {
            max = this->data[1];
            this->data[1] = this->data[size];
            this->size--;
            MaxHeapify(1);
        }
        return max;
    }

private:
    /**
     * 对节点cur进行大堆化
     * @param cur
     */
    void MaxHeapify(int cur) {
        // 左右孩子节点的下标
        int lChildIndex = GetLChild(cur);
        int rChildIndex = GetRChild(cur);
        // 求出结点及其左右节点中最大的值的下标
        int maxIndex = cur;
        maxIndex = (lChildIndex > 0 && this->data[lChildIndex] >
                                       this->data[cur]) ? lChildIndex : maxIndex;
        maxIndex = (lChildIndex > 0 && this->data[rChildIndex] >
                                       this->data[maxIndex]) ? rChildIndex : maxIndex;

        // 当前结点并非最大则与最大的子结点交换
        if (maxIndex != cur) {
            std::swap(this->data[cur], this->data[maxIndex]);
            MaxHeapify(maxIndex);
        }
    }

    /**
    * 对节点cur进行小堆化
    * @param cur
    */
    void MinHeapify(int cur) {
        // 左右孩子节点的下标
        int lChildIndex = GetLChild(cur);
        int rChildIndex = GetRChild(cur);
        // 求出结点及其左右节点中最小的值的下标
        int minIndex = cur;
        minIndex = (lChildIndex > 0 && this->data[lChildIndex] <
                                       this->data[cur]) ? lChildIndex : minIndex;
        minIndex = (rChildIndex > 0 && this->data[rChildIndex] <
                                       this->data[minIndex]) ? rChildIndex : minIndex;

        // 当前结点并非最大则与最大的子结点交换
        if (minIndex != cur) {
            std::swap(this->data[cur], this->data[minIndex]);
            MinHeapify(minIndex);
        }
    }
};

#endif //ALDS_HEAP_H
